package com.chj.jz.dp.class06;
//https://www.jiuzhang.com/problem/distinct-subsequences/#tag-lang-java
public class Code04_DistinctSubsequences {
	 public static int numDistinct(String s, String t) {
	        if(s.equals(t)){
	            return 1;
	        }
	        
	        char[] s1 = s.toCharArray();
	        char[] s2 = t.toCharArray();
	        int m = s1.length;
	        int n = s2.length;
	        int[][] f = new int[m + 1][n + 1];
	        // 代表 s.substring(0 , i) 和 t.substring(0 ，j) 的最大distinct答案
//	        for(int i = 0 ; i <= m ; i++){
//	            f[i][0] = 1;
//	            //t 为 “”  s有一种变成 “” 全删了
//	        }
	        for(int i = 0 ; i <= m ; i++){
	            for(int j = 0 ; j <= n ; j++){
	            	
	            	if(j == 0) {
	            		f[i][j] = 1;
	            		continue;
	            	}
	            	
	            	if(i == 0) {
	            		f[i][j] = 0;
	            		continue;
	            	}
	            	
	            	 f[i][j] = f[i - 1][j];
	            	
	                if(s1[i - 1] == s2[j - 1]){
	            // 去前面s找有匹配的个数          只和当前的i 匹配                 
	                    f[i][j] += f[i - 1][j - 1] ;
	                }
//	                else{          //去前面s找有匹配的个数
//	                    f[i][j] = f[i - 1][j];
//	                }
	            }
	        }
	        return f[m][n];        

	    }
	 
	 public static void main(String[] args) {
			// 输入: "ABCD" and "EDCA"
			{
				String str1 = "rabbbit";
				String str2 = "rabbit";
				System.out.println(numDistinct(str1, str2));
			}
			{
				String str1 = "abcd";
				String str2 = "";
				System.out.println(numDistinct(str1, str2));
			}
		}
}
